package problems.daily;

import java.util.Arrays;

/**
 * 1658. 将 x 减到 0 的最小操作数
 * <p>https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/</p>
 *
 * @author habitplus
 * @since 7:59, 2023/1/7
 */
public class DT1658 {
    /*
     * 滑动窗口
     */
    public int  minOperations(int[] nums, int x) {

        int sum = Arrays.stream(nums).sum();

        if (sum < x) return -1;

        int n = nums.length;
        int right = 0;
        int lsum = 0, rsum = sum;
        int ret = n + 1;

        for (int left = -1; left < n; ++left) {
            if (left != -1) {
                lsum += nums[left];
            }

            while (right < n && lsum + rsum > x) {
                rsum -= nums[right];
                ++right;
            }

            if (lsum + rsum == x) {
                ret = Math.min(ret, (left + 1) + (n - right));
            }
        }

        return ret > n ? -1 : ret;
    }
}
